﻿using System;
using System.Collections.Generic;
using Library.Collections.Generic;
using INDEX = System.UInt64;

namespace Library.Linq
{
    public static class DepthFirst
    {
        public static IEnumerable<IEnumerable<TNode>> AsEnumerable<TNode>(TNode tree)
            where TNode : ITreeReadOnly<TNode>
        {
            return AsEnumerable(tree, new Library.Collections.Generic.Stack<TNode>());
        }

        public static IEnumerable<IEnumerable<TNode>> AsEnumerable<TNode>(TNode tree, IStack<TNode> stack)
            where TNode : ITreeReadOnly<TNode>
        {
            IEnumerator<TNode>[] _stack = new IEnumerator<TNode>[0];
            IEnumerator<TNode> enumerator;
            int count = 0;

            try
            {
            label1:
                if (stack.Push(tree))
                {
                    yield return (IEnumerable<TNode>)stack.Clone(Direction.Reverse, Access.Read);
                    enumerator = tree.Children.GetEnumerator();
                    if (count == _stack.Length)
                    {
                        Array.Resize(ref _stack, count == 0 ? 4 : count * 2);
                    }
                    _stack[count++] = enumerator;
                }
                else
                {
                    if (count == 0) yield break;
                    enumerator = _stack[count - 1];
                }
            label2:
                if (enumerator.MoveNext())
                {
                    tree = enumerator.Current;
                    goto label1;
                }
                else
                {
                    if (count > 0)
                    {
                        _stack[--count] = null;
                    }
                    enumerator.Dispose();
                    stack.Pop();
                    if (count == 0) yield break;
                    enumerator = _stack[count - 1];
                    goto label2;
                }
            }
            finally
            {
                while (count > 0)
                {
                    _stack[--count].Dispose();
                }
            }
        }
    }
}
